Path sum

Time: O(N); Space: O(H); easy

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note:

  • A leaf is a node with no children.

Example 1:

Input: root = {TreeNode} [5,4,8,11,None,13,4,7,2,None,None,None,1], sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

Output: True

Explanation:

  • There exist a root-to-leaf path 5->4->11->2 which sum is 22.

Example 2:

Input: root = {TreeNode} [5,4,8], sum =18

Output: False

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Recursion [O(N), O(H)]

[5]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of BinartTree
    """
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: boolean
        """
        if root is None:
            return False

        if root.left is None and root.right is None and root.val == sum:
            return True

        return self.hasPathSum(root.left, sum - root.val) or \
               self.hasPathSum(root.right, sum - root.val)

[8]:

s = Solution1()

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(1)
sum = 22
assert s.hasPathSum(root, sum) == True

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
sum = 17
assert s.hasPathSum(root, sum) == False